package com.leetcode.offer.chapter3;

import com.leetcode.basic.ListNode;

import java.util.HashSet;
import java.util.Set;

/**
 * @author Dennis Li
 * @date 2020/7/13 14:39
 */
public class MeetingNode_23 {

    public ListNode meetingNode(ListNode head) {
        Set<ListNode> set = new HashSet<>();
        while (head != null) {
            if (set.contains(head))
                return head;
            set.add(head);
            head = head.next;
        }
        return null;
    }

    public ListNode meetingNode2(ListNode head){
        // 快慢指针
        if(head == null) return null;
        ListNode fast = head;
        ListNode slow = head;
        boolean loop = false;
        // 看是否有环
        while(fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if(slow == fast) {
                loop = true;
                break;
            }
        }
        if(!loop) return null; //没有环
        // 计算环中结点个数
        int num = 1; // 环中结点个数
        fast = fast.next;
        while(fast != slow){
            fast = fast.next;
            num++;
        }
        // 再次执行快慢指针遍历，找到相遇结点，即是入口结点
        fast = head;
        slow = head;
        for (int i = 0; i < num; i++) {
            fast = fast.next;
        }
        while(fast != slow){
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }

}
